|
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size. It is an optimization problem that belongs to the class of covering problems and can be solved in polynomial time. == Definition == Formally, an edge cover of a graph ''G'' is a set of edges ''C'' such that each vertex in ''G'' is incident with at least one edge in ''C''. The set ''C'' is said to ''cover'' the vertices of ''G''. The following figure shows examples of edge coverings in two graphs. :File:Edge-cover.svg A minimum edge covering is an edge covering of smallest possible size. The edge covering number is the size of a minimum edge covering. The following figure shows examples of minimum edge coverings. :File:Minimum-edge-cover.svg Note that the figure on the right is not only an edge cover but also a matching. In particular, it is a perfect matching: a matching ''M'' in which each vertex is incident with exactly one edge in ''M''. A perfect matching (if it exists) is always a minimum edge covering. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Edge cover」の詳細全文を読む スポンサード リンク
|
